Квадратичный дискриминантный анализ (QDA)

Квадратичный дискриминантный анализ (Quadratic Discriminant Analysis, QDA) — это метод генеративной классификации, который базируется на предположении о том, что признаки каждого класса распределены согласно многомерному нормальному закону:

$$p(\boldsymbol{x} | y=c) = \mathcal{N}(\boldsymbol{\mu}_c, \Sigma_c)$$

Каждый класс имеет свою собственную матрицу ковариации $\Sigma_c$, что означает, что форма и ориентация «облака» точек могут существенно различаться от класса к классу.

Дискриминантная функция

Как было показано в предыдущей главе, в генеративном подходе прогноз строится через максимизацию рейтинга $g_c(\boldsymbol{x}) = \ln p(\boldsymbol{x}|y=c) + \ln p(y=c)$.

Плотность многомерного нормального распределения имеет вид:

$$p(\boldsymbol{x} | y=c) = \frac{1}{(2\pi)^{D/2} |\Sigma_c|^{1/2}} \exp \left( -\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_c)^T \Sigma_c^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_c) \right)$$

Выведем дискриминантную функцию, подставив плотность в логарифм и отбросив константу $-\frac{D}{2} \ln (2\pi)$, которая не влияет на результат сравнения:

$$g_c(\boldsymbol{x}) = \ln p(y=c) - \frac{1}{2} \ln |\Sigma_c| - \frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_c)^T \Sigma_c^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_c)$$

Раскроем квадратичную форму в последнем слагаемом:

$$g_c(\boldsymbol{x}) = \ln p(y=c) - \frac{1}{2} \ln |\Sigma_c| - \frac{1}{2} \left( \boldsymbol{x}^T \Sigma_c^{-1} \boldsymbol{x} - 2\boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{x} + \boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{\mu}_c \right)$$

Итоговое выражение для квадратичной дискриминантной функции:

$$g_c(\boldsymbol{x}) = -\frac{1}{2} \boldsymbol{x}^T \Sigma_c^{-1} \boldsymbol{x} + \boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{x} - \frac{1}{2} \boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{\mu}_c - \frac{1}{2} \ln |\Sigma_c| + \ln p(y=c)$$

Так как функция содержит слагаемое $\boldsymbol{x}^T \Sigma_c^{-1} \boldsymbol{x}$, граница между любыми двумя классами $g_i(\boldsymbol{x}) = g_j(\boldsymbol{x})$ представляет собой квадратичную поверхность.

Аналитическое решение

Преимуществом метода является существование аналитического решения при настройке параметров методом максимального правдоподобия, что делает настройку модели быстрой.

Сложность модели и число параметров

QDA является достаточно гибким методом, что обусловлено большим количеством настраиваемых параметров. Для каждого класса $c \in \{1, \dots, C\}$ необходимо оценить:

• априорную вероятность $\pi_c=p(y=c)$ ($1$ параметр);
• вектор средних $\boldsymbol{\mu}_c$ ($D$ параметров);
• симметричную матрицу ковариации $\Sigma_c$ ($D(D+1)/2$ уникальных параметров).

Суммарное число параметров модели составляет:

$$C \cdot \left( 1 + D + \frac{D(D+1)}{2} \right)$$

При большой размерности признаков $D$ количество параметров растёт квадратично, что может привести к быстрому переобучению (overfitting), особенно если данных в конкретном классе мало.

Также заметим, что необходимость обращения ковариационных матриц для каждого класса имеет вычислительную сложность $O(C \cdot D^3)$.

Регуляризация

При высокой размерности признаков $D$ или малом объёме обучающей выборки $N$ выборочные ковариационные матрицы $\Sigma_y$ становятся плохо обусловленными (ill-conditioned) или вовсе вырожденными. В таких случаях для обеспечения устойчивости модели применяется регуляризованный дискриминантный анализ (Regularized Discriminant Analysis, RDA), основанный на методе сжатия (shrinkage) оценок ковариационных матриц.

Задача

Докажите, что в случае, если количество признаков больше числа объектов ($D > N$), матрица $\Sigma_y$ будет вырожденной, что делает невозможным вычисление обратной матрицы $\Sigma_y^{-1}$ в стандартном QDA.

Основная идея регуляризации заключается в линейном комбинировании (смешивании) исходной матрицы с более стабильными структурами. Для этого используют коэффициент регуляризации $\alpha \in [0, 1]$ для управления степенью этого смешивания.

Индивидуальные ковариационные матрицы классов $\Sigma_y$ смешиваются с общей ковариационной матрицей $\Sigma$ для всех данных:

$$\Sigma'_y(\alpha) = (1 - \alpha) \Sigma_y + \alpha \Sigma$$

При $\alpha = 1$ модель QDA полностью переходит в LDA, что резко сокращает число оцениваемых параметров и снижает риск переобучения.

Для ещё большей устойчивости в формуле выше вместо матрицы $\Sigma$ подставлять её смесь с единичной матрицей, умноженной на общую дисперсию данных:

$$\Sigma \to (1 - \beta) \Sigma + \beta \sigma^2 I,\quad \beta\in [0,1]$$

Задача

Покажите, что $\sigma^2 = \text{tr}(\Sigma)/D$.

Такое преобразование гарантирует, что матрица станет положительно определённой и легко обратимой.

Геометрический смысл

Увеличение $\alpha$ приводит к тому, что ориентация и форма эллипсоидов рассеяния всех классов становятся всё более одинаковыми для всех классов.

Увеличение $\beta$ заставляет эллипсоиды становиться более круглыми, подавляя информацию о корреляциях между признаками. Это гарантирует устойчивость расчётов, так как итоговая матрица избавляется от околонулевых собственных чисел.

Гиперпараметры $\alpha$ и $\beta$ следует подбирать по валидационной выборке.

Частные случаи

Для снижения сложности модели часто вводят дополнительные ограничения на вид матриц ковариации $\Sigma_c$:

Диагональные матрицы

Предполагается, что признаки внутри класса линейно независимы. В этом случае $\Sigma_c = \text{diag}(\sigma_{c,1}^2, \dots, \sigma_{c,D}^2)$. В результате число параметров $\Sigma_c$ сокращается с $O(D^2)$ до $O(D)$.

QDA с диагональными ковариационными матрицами также называется гауссовским наивным байесовским классификатором (Gaussian Naive Bayes), поскольку нескоррелированность признаков в случае их совместного нормального распределения эквивалентна их независимости при условии класса.

Сферические матрицы

Предполагается, что все признаки не только независимы, но и обладают одинаковой дисперсией $\Sigma_c = \sigma_c^2 \boldsymbol{I}$. В этом случае вместо $O(D)$ параметров для каждой ковариационной матрицы нужно оценить всего один - $\sigma_c^2$.

Классификация в этом случае сводится к поиску ближайшего центра класса $\boldsymbol{\mu}_c$ с учётом разброса точек каждого класса и с поправкой на его частотность.

Одинаковые матрицы ковариации

Предполагается, что ковариационные матрицы всех классов совпадают с общей ковариацией всех данных $\Sigma$:

$$\Sigma_1=\Sigma_2=...=\Sigma_C=\Sigma$$

В этом случае метод называется линейным дискриминантным анализом (Linear Discriminant Analysis, LDA).

Число параметров для оценки ковариационных матриц снижается с $O(CD^2)$ до $O(D^2)$, а сама оценка ковариации становится более устойчивой к шуму и нехватке данных, чем индивидуальные оценки в QDA. Это преимущество становится особенно важным, когда количество объектов в некоторых классах невелико.